500 billion
billion moves later, computers solve checkers
19.07.2007
– For almost twenty years now Jonathan Schaeffer, a professor at the
University of Alberta in Canada, has been working on checkers. His program
Chinook won the world championship against the best humans, after which he went
about solving the game completely. We interview him and ask about the potential
to solve chess. In the initial position of the game of checkers is a draw.
It took thirteen years of brute-force computer analysis to examine all 500 billion billion possible board positions, but today (Thursday, July 19, 2007) researchers at the University of Alberta in Canada formally announced that they had finally solved the centuries-old game of checkers. Specifically: they had a file which contained full information on every legal position that can arise during the game, and which move, if any, will lead to a win or a draw in that position.
The conclusion to be drawn from the completion of the database: with perfect play by both sides checkers cannot be won or lost. The game will inevitably end in a draw. This means that even the most skilled player cannot beat a computer which has access to the database. The computer can't win either – it can only do so if the human opponent makes a mistake that leads to position that is classified as a loss in the database.
Prof. Jonathan Schaeffer, 2004 in Israel
The task of solving checkers was undertaken and completed by Prof. Jonathan Schaeffer, who has been at it for close to twenty years. He developed the program Chinook in 1989 (together with Rob Lake, Paul Lu, Martin Bryant, Norman Treloar and others). Chinook was the first computer program to win the world champion title in a competition against humans. After a number of further successes in competitive play Schaeffer decided to concentrate on the problem of solving the game comprehensively.
"Checkers has a search space of 5x1020, a daunting number," Schaeffer says. "Almost continuously since 1989 (with a gap in the 1997 to 2001 period), dozens of computers have been working around the clock to solve the game. You’ve got 500 billion billion pieces of hay in your haystack, and you’ve got to find the needles.“
Playing a game of blitz against child prodigy Murugan Tiruchelvam in London
2000
One would do well to note that solving checkers was not victory of pure machine intelligence, but one based largely on rote calculating ability. Nevertheless: "It's a milestone," said Murray Campbell, co-inventor of the chess program Deep Blue. "He's stretched the state of the art."
For those of you who don't know already, Checkers ("draughts" in Ireland and the UK) is played on 8x8 board, pieces move diagonally forward, one square at a time, and capture by jumping over and enemy piece. If a piece reaches the back rank, it is promoted to a king, which can move backwards as well as forwards. Other versions of the game, such as "Damen" in Germany are more popular in Europe and Russia.
From a mathematical game theory point of view, checkers is a simpler game than chess. There are only 5x1020 positions (5 with 20 zeros after it) in checkers, whereas chess has at least 1040 positions. Thus, we have a better chance of completely solving checkers than chess. However, that does not mean that checkers is easier (or harder) to play than chess.
The best player for the last decade has been Chinook, a program developed by Dr. Jonathan Schaeffer. It won the title "Man-Machine World Champion" from Dr. Marion Tinsley, in 1994. Chinook would not be what it is today without Tinsley.
|
|
Marion Tinsley was an amalgam of the longevity of Lasker, the invincilibility of Petrosian and the perfection of Fisher. His career is unique in any game or sport. From 1950 to 1995 Tinsley never lost a single tournament, or even shared first place with another player. He took part in nine world championship matches, winning them all, usually by an embarrassingly large margin. In the 45-year period he played in thousands of tournaments, matches and exhibitions, playing many tens of thousands of games. Of these he lost exactly seven games. "Tinsley was as close to perfect as is humanly possible," writes Jonathan Schaeffer.
By 1990, Tinsley had grown bored playing humans and looked for new challenges. He agreed to play Chinook, then the strongest computer player. The ACF (American Checkers Federation) and the EDA (English Draughts Association) had different ideas and refused to allow the match. Tinsley put the cat amongst the pigeons, resigned his title, and signed a contract to play Chinook.
The ACF and the EDA came to their senses and created the "Man-Machine World Championship". This matched the best human against the best computer. Tinsley won the first match in 1992 with 4 wins, 2 losses and 33 draws. The rematch began in 1994 against a much stronger program running on better hardware. After six draws, Tinsley resigned the match on grounds of ill health. He died a year later from cancer.
|
|
In 1994, Chinook ran on a 16 processor Silicon Graphics Challenge computer. The processors ran at 150 Mhz (very fast in 1994, very slow in 2003) with 1 GB of RAM. This is equivalent to a 2.4 GHz Pentium that are common enough today, but it was a phenomenal piece of hardware in 1994. The program also had access to eight-piece tablebases for perfect endgame play. The machine searched a minimum of 19 ply.
During their preparations the Chinook team came across one interesting result: "Experiments in Chinook show that there comes a point where increased search depth provides diminishing returns." In particular, Chinook played better checkers with a 19 ply rather than a 21 or 23 ply search.
So, what does all this mean for chess? Can we extrapolate these results from one checkers playing programs to chess playing programs? Certainly, Chinook and Fritz use similar search algorithms. They each have a positional evaluation function. They each take advantage of table bases for evaluating endgames. The big difference is the number of positions possible in each game: 1020 for checkers and 1040 for chess. To get some idea of this, if a computer could solve checkers completely in one nanosecond (a single cycle of a 1 GHz computer), it would take this computer 3000 years to solve chess.
The second difference is the usefulness of tablebases. Chinook has access to eight-piece endings (now ten-pieces). The chess playing programs now commonly use five-piece table bases, and six-piece table bases are starting to be generated. Chinook would regularly be able to decide the outcome of the game by move five, searching 19 ply ahead and looking up the eight-piece ending in its table bases. This does not happen in chess. Even at move 40 this does not happen. However, starting with 16 pieces instead of 12, and accessing five-piece endings instead of eight is too great a difference to overcome in the near future.
